package com.ljy.my_study.lintcode.线段树;

/**
 * @author James
 * @date 2018年4月12日
 */
public class SegmentTreeMain2 {
	public static void main(String[] args) {
//		Integer[] nums= {1,null,3,4};
		Integer[] nums= {null,null,null,null,null,null,null,null,null,null,1};
		SegmentTreeNode node = build(nums,0, nums.length-1);
		System.out.println(node);
		System.out.println("---------------------");
//		System.out.println(query(node,1,1));
//		System.out.println(query(node,1,2));
//		System.out.println(query(node,2,3));
		System.out.println(query(node,1,10));
		System.out.println(query(node,9,10));
		System.out.println(query(node,11,12));
	}

	// 建立SegmentTreeNode
	public static SegmentTreeNode build(Integer[] nums,int start,int end) {
		if (start > end) {
			return null;
		}
		if (start == end) {
			return new SegmentTreeNode(start, end,nums[start]==null?0:1);
		}
		SegmentTreeNode node = new SegmentTreeNode(start, end);
		int leftNodeLeftIndex = start;
		int leftNodeRightIndex = (start + end) / 2;
		int rightNodeLeftIndex = (start + end) / 2 + 1;
		int rightNodeRightIndex = end;
		node.left = build(nums,leftNodeLeftIndex, leftNodeRightIndex);
		node.right = build(nums,rightNodeLeftIndex, rightNodeRightIndex);
		node.count=node.left.count+node.right.count;
		return node;
	}

	// 查询SegmentTreeNode
	public static int query(SegmentTreeNode node,int start,int end) {
		int result=0;
		if(node==null) {
			return result;
		}
		int nodeStart=node.start;
		int nodeEnd=node.end;
		if(start<nodeStart) {
			start=nodeStart;
		}
		if(end>nodeEnd) {
			end=nodeEnd;
		}
		if(end<nodeStart||start>nodeEnd) {
			return 0;
		}
		if(nodeStart==start&&nodeEnd==end) {
			return node.count;
		}
		int leftNodeStart=node.left.start;
		int leftNodeEnd=node.left.end;
		int rightNodeStart=node.right.start;
		int rightNodeEnd=node.right.end;
		if(end<=leftNodeEnd) {
			result+=query(node.left,start,end);
		}else if(start>=rightNodeStart) {
			result+=query(node.right,start,end);
		}else {
			result+=query(node.left,start,leftNodeEnd);
			result+=query(node.right,rightNodeStart,end);
		}
		return result;
	}
}
